package wh.重复元素2;

import java.util.*;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/12/30 22:16
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,1};
        boolean b = containsNearbyDuplicate3(arr, 3);
        System.out.println(b);
    }

    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = new ArrayList<>();
            if (map.containsKey(nums[i])){
                map.get(nums[i]).add(i);
            }else {
                list.add(i);
                map.put(nums[i],list);
            }
        }


        Collection<List<Integer>> values = map.values();
        for (List<Integer> list : values){
            if (list.size() > 1){
                for (int i = list.size()-1; i >= 0; i--) {
                    if (i == 0){
                        break;
                    }else if (list.get(i)-list.get(i-1) <= k){
                        return true;
                    }
                }
            }
        }
        return false;
    }


    //妙啊
    public static boolean containsNearbyDuplicate2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (map.containsKey(num) && i - map.get(num) <= k) {
                return true;
            }
            map.put(num, i);
        }
        return false;
    }

    public static boolean containsNearbyDuplicate3(int[] nums, int k) {
        Set<Integer> set = new HashSet<Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (i > k) {
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }

    //和上面类似
    public boolean containsNearbyDuplicate4(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
            if(set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }

}
